The present invention is directed to communications networks. It particularly concerns congestion avoidance.
Internetwork communications are based on operations of routers, which are network devices that determine, on the basis of destination information in packets that they receive, where to forward the packets so that they are likely to reach the intended destinations.
Router configurations vary widely, but that of FIG. 1 is typical. Router 10 includes a plurality of communications interfaces 12, 14, and 16, which send and receive communications packets to and from remote locations. When one of the interface modules receives an incoming packet from a remote location, it places header information from that packet onto an internal communications bus 18 by which it communicates with a forwarding engine 20 that determines where the packet should be sent. The interfaces and forwarding engine can be implemented in respective high-performance processors 21 and storage circuitry 22 that contains program instructions that configure the processors to act together as a router. The programming for such implementations is typically provided in some type of persistent medium, such as a magnetic disk or semiconductor read-only memory. That type of implementation most often executes that programming after it has been transferred to a volatile medium, such as dynamic or static random-access memory. The drawing shows the storage circuitry 22 as separate media for each interface or forwarding engine, but some configurations may additionally, or instead, employ common storage. In some cases the router""s programming may be updated remotely by sending it electrical or other signals that represent the instructions.
To maximize speed capacity, other routers are implemented wholly or largely in xe2x80x9crandom logicxe2x80x9d instead of general-purpose processors. The xe2x80x9cprogrammingxe2x80x9d in such implementations is ordinarily hard-coded in the circuitry""s structure, but read-only or read/write storage media may be employed in such implementations, too, to affect the router""s behavior. Once the decision has been made, an output packet is formed from the input packet by packet-assembly circuitry that may reside in one or more of the interface modules and/or the forwarding engine, and the forwarding engine causes another interface to send the output packet to a further remote location.
Some routers may actually be implemented in switches that employ the Asynchronous Transfer Mode (ATM) protocol. Such switches operate in the manner that FIG. 2 depicts. Suppose that one of router 10""s ATM interfaces provides communication with another router 24, while a different ATM interface provides communication with a further router 26. Suppose further that router 10 is an xe2x80x9cedge routerxe2x80x9d of an internet-service provider: although it is part of a network that is maintained by the service provider, it has direct links to client routers such as router 26, which are outside the service-provider network.
Router 26 sends information in packets to router 10, and we will assume for present purposes that the packets sent by router 26 conform to the Internet Protocol (IP). In accordance with that protocol, each packet begins with a header that includes, among other information, an address that indicates the host system to which the packet should ultimately be routed. Router 10 includes storage circuitry containing a routing table that tells the router the direction in which to send the packet so that it will reach the destination set forth in the IP header.
Now, the service provider must of necessity base its initial routing decision on the incoming packet""s destination address. But IP addressing makes doing so in the conventional manner a relatively time-consuming process. An IP address is typically 32 bits long: it could theoretically distinguish over four billion host systems. Although the number of host systems that have globally unique IP addresses is much smaller than this, the actual number of such systems is considerably greater than the number of entries it is practical for an individual router""s forwarding table to include.
Many of the forwarding table""s entries therefore are directed not to a single host address but rather to a xe2x80x9cprefixxe2x80x9d of fewer than the thirty-two bits. Such an entry indicates that the forwarding information contained in it can be used to reach any destination address that begins with the prefix to which the entry is directed. Prefixes vary in length, the longest being the most specific and thus presumably representing the best routes to the included host addresses. So a router that receives an IP packet searches through its forwarding table to find the longest prefix that matches the incoming packet""s destination address, and it forwards the packet in accordance with the information thus found.
Such longest-match searches are time-consuming. But an Internet-service provider""s xe2x80x9ctransitxe2x80x9d routers, i.e., those that are not edge routers, can avoid such an expensive longest-match search if they forward the packets in ATM xe2x80x9ccells.xe2x80x9d An ATM cell includes a xe2x80x9cvirtual-channel identifier,xe2x80x9d which identifies the receiving router""s forwarding-table entry that contains the forwarding information for the xe2x80x9cvirtual channelxe2x80x9d along which the cell is to be forwarded. For this purpose, an edge router such as router 10 works with other routers to set up a virtual channel within the service-provider network before it forwards the first packet to a particular destination. That is, successive routers determine the path through the network that such packets should take, and they tell each other where in their respective forwarding tables they keep forwarding information for that virtual circuit.
FIG. 3 depicts the format that ATM switches use to send information over the resultant virtual channel. From the point of view of an ATM client, the frame that FIG. 3""s third row depicts is the basic transmission unit. (Those skilled in the art will recognize that there are also other possible ATM frame formats, but FIG. 6""s third row depicts one, known as xe2x80x9cAAL5,xe2x80x9d that would typically be employed for user data.) Since the service-provider network is being used to forward IP datagrams from router 26, that drawing""s fourth row depicts the frame""s payload as an IP datagram having the usual IP header and IP data.
From the point of view of such an ATM switch, though, the (variable-length) third-row frame is not the basic transmission unit. Specifically, the edge router divides that frame into pieces that it forwards in a plurality of equal-sized cells. As FIG. 3""s second row shows, an ATM cell consists of a cell payload and header. FIG. 3""s first row depicts the cell""s header format and shows that it includes a PTI field. One purpose of the PTI field is to indicate whether the cell containing it is the last one in a frame. If it is, then the cell""s last eight bytes form the frame trailer field depicted in FIG. 3""s third row. Among other things, the trailer indicates how much of the preceding cell""s contents is not actual frame payload but instead is fill used to pad the cell to the predetermined ATM cell size.
The header field of particular interest here is the VPI/VCI field. Each switch associates a virtual path or virtual channel with a virtual-path or virtual-channel identifier of local significance to that switch: it indicates the forwarding-table entry from which the switch is to fetch forwarding information for the cell being forwarded. Part of that entry""s information is a replacement for the incoming cell""s virtual-path or virtual-channel identifier. The replacement specifies the virtual path or virtual channel""s correct entry in the forwarding table of the xe2x80x9cnext-hopxe2x80x9d switch, to which the current switch""s forwarding-table entry directs that the cell be sent.
Suppose that the client router 26 of FIG. 2 sends edge router 10 a packet whose IP destination address is D1. Also suppose that a further client router 28 provides access to that destination. The service-provider router having a direct link to client router 28 is router 30. To forward the packet properly, the provider network sets up an ATM virtual path from router 10 through routers 24 and 32 to router 30. Router 10 then divides packets specifying destination D1 into ATM cells, and it places into each such cell""s header the virtual-path identifier V1 that router 10 learned during the virtual-channel-establishment process was the location in router 24""s forwarding table where router 24 stored the proper forwarding information for the virtual channel to router 30. So router 24 does not need to perform a longest-match search when it receives such cells: it goes directly to the table entry that virtual-path identifier V1 specifies, and that entry tells it both the interface over which to forward the cell and the virtual-channel identifier V2 with which it should replace the incoming cell""s virtual-channel identifier V1.
Similarly, router 32 employs virtual-channel identifier V2 to find its forwarding-table entry for that virtual channel. That entry tells router 32 to forward the cell over its interface with the link to router 30 and to place the value V3 into that cell""s VPI/VCI field. Since router 30 is an edge router and must forward the packet to a non-ATM router 28, it assembles the IP-packet-containing frame from its constituent cells and forwards that IP packet, which still contains its destination address D1, to client router 28.
A similar sequence of events occurs when another customer router 34 sends an IP datagram containing destination address D1 to another edge router 36. As before, each of the routers along the service provider""s path toward destination D, allocates a virtual-channel identifier to that virtual channel. Edge router 36 encapsulates the datagram in an ATM frame and divides the frame into fixed-length cells whose virtual-channel identifier is, say, V4. Subsequent routers 40 and 32 forward such cells, replacing their virtual-channel identifiers with values V5 and V6, respectively. And, as before, the egress edge router 30 re-assembles the IP datagram and sends it to the customer router 28 that can forward it on to its ultimate destination.
Note that routers 30 and 32 in this scenario allocate two different virtual-channel identifiers to a common-destination path; they do not xe2x80x9cmergexe2x80x9d the channels by assigning a common virtual-channel identifier. This scenario is typical, even though virtual-channel identifiers are a relatively scarce resource in ATM switches.
We have recognized that a principal impediment to merging virtual channels, and thus conserving the virtual-channel-identifier space, can be eliminated by simply employing a feature that many ATM switches already provide in other contexts in order to shorten congestion-avoidance control loops.
To avoid congestion, many ATM systems employ an available-bit-rate (ABR) mechanism. In accordance with this mechanism, an ingress ATM switch that sends data into a particular virtual channel intersperses so-called resource-management cells among the data cells sent into that virtual channel. Unlike data cells, a resource-management cell travels not only in one direction along the virtual channel but also back again to the ingress switch that initially created it.
When the ingress router creates the resource-management cell, it includes an xe2x80x9cexplicit-ratexe2x80x9d value in it. The explicit-rate value specifies the rate at which it proposes to send cells into that virtual channel. As the resource-management cell traverses the virtual channel, the virtual channel""s routers determine whether they can sustain the rate that the resource-management cell""s explicit-rate value specifies. If not, they reduce the explicit-rate entry to a value that they can sustain. So the returned resource-management cell tells the ingress router a rate at which it can transmit cells into that virtual channel without overwhelming any of that virtual channel""s routers.
This resource-management-cell use has been an impediment to virtual-channel merging, since resource-management cells must traverse the virtual channel in the reverse direction as well as in the forward direction, and virtual-channel-indicator swapping at the merge eliminates information that would identify the resource-management cell""s source; the reverse-directed cell has nothing in it to identify the constituent channel into which the merging router should direct that cell. But we have recognized that a solution to this problem can be provided by using a mechanism that many ATM switches use to shorten the control loops that lengthy virtual channels represent.
Specifically, one or more ATM switches in the midst of a long virtual channel can act as xe2x80x9cvirtual destinationsxe2x80x9d and xe2x80x9cvirtual sources.xe2x80x9d That is, rather than forwarding a resource-management cell to the next router in the virtual channel, a switch acting as a virtual destination sends it back toward the source. The source switch also acts as a virtual source by sending another resource-management cell in the forward direction to the next switch in the virtual channel.
In accordance with our invention, an ATM switch merges constituent virtual channels but acts as a virtual destination/virtual source for those virtual channels""resource-management cells. In this way, no merge occurs in the part of a virtual channel that any individual resource-management cell traverses, so the available-bit-rate mechanism is no longer an impediment to virtual-channel merging. This invention is applicable not only to ATM-implemented networks but also label-switching networks implemented in other technologies.